package com.pan.alg.niuke.stackque;

import java.util.Stack;

/**
 * 描述
 * 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
 * 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
 *
 * 数据范围：字符串长度 0\le n \le 100000≤n≤10000
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 */
public class BracketIsValid {

    /**
     *  []{[()()()]}
     * @param s string字符串
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        Stack<Character> rightStack = new Stack<>();
        char[] chars = s.toCharArray();
        boolean isValid = true;
        for (int i = 0; i < chars.length; i++) {
            char current = chars[i];
            if('['==current){
                rightStack.push(']');
            } else if('{'==current){
                rightStack.push('}');
            } else if('('==current){
                rightStack.push(')');
            }else{
                if(rightStack.empty()){
                    isValid=false;
                    break;
                }
                Character pop = rightStack.pop();
                if(!pop.equals(current)){
                    isValid=false;
                    break;
                }
            }
        }
        if(isValid){
            isValid = rightStack.empty();
        }
        return isValid;
    }

    public static void main(String[] args) {
        String test= "[{[()()()]}";
        BracketIsValid bracketIsValid = new BracketIsValid();
        boolean valid = bracketIsValid.isValid(test);
        System.out.println(valid);
    }
}
